//author :junix
#include <iostream>
#include <cstring>

int* kmp_table(const char *pattern) {
	int size = strlen(pattern);
	int *table = new int[size];
	
	int i=0;
	table[0] = -1;
	int j = -1;

	while (i<size) {
		while ( j>-1 && pattern[i]!=pattern[j])
			j = table[j];

		++i;
		++j;
		
		if (pattern[i]==pattern[j])
			table[i] = table[j];
		else
			table[i] = j;
	} 

	return table;
}

void KMP(const char *text, const char *pattern) {
	int *table = kmp_table(pattern);
	int ts = strlen(text);
	int ps = strlen(pattern);
	int ti = 0;
	int pi = 0;
	while (ti<ts) {
		while (pi>-1 && text[ti]!=pattern[pi])
			pi = table[pi];

		pi++;
		ti++;	
		
		if (pi==ps) {
			std::cout<<"Found a match:"<<text+ti-ps<<std::endl;
			pi = table[pi];
		}
	}
}

int main(){
	const char *text = "hello,junix.My name is junix. OK??";
	const char *pattern = "junix";
	KMP(text,pattern);
}
